package main

import (
	"fmt"
	"math/rand"
)

const N int = 1e6 + 10

var (
	q [N]int64
	n int
)

func quickSort(l int, r int) {
	if l >= r {
		return
	}
	x := q[(l+r) >> 1]
	i := l - 1
	j := r + 1
	for i < j {
		i++
		for q[i] < x {
			i++
		}
		j--
		for q[j] > x {
			j--
		}
		if i < j {
			temp := q[i]
			q[i] = q[j]
			q[j] = temp
		}
	}
	quickSort(l, j)
	quickSort(j+1, r)
}

func main() {
	for i:=0;i<10;i++ {
		q[i] = int64(rand.Intn(100))
	}
	for i := 0;i<10;i++ {
		fmt.Printf("%d ",q[i])
	}
	fmt.Println()
	quickSort(0, 9)
	for i := 0;i<10;i++ {
		fmt.Printf("%d ",q[i])
	}
}
